package com.bruce.leetcode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

/**
 * 无重复字符的最长子串
 * <p>给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。<p/>
 * <p>https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/<p/>
 * <br>CreateDate  2021/11/22 18:10:16
 *
 * @author luotuan
 * @version 1.0.0
 */
public class MaxLongSubStr {
    public static int lengthOfLongestSubstring(String s){
       if(s.length()<=0 || s==null){
           return 0;
       }
       Set<Character> set = new HashSet<>();
       // 右侧下标
       int point = 0;
       int max = 0;
       int n = s.length();
       for(int i =0;i<n;i++){
           if(i!=0){
               //移除上一个元素
               set.remove(s.charAt(i-1));
           }
           while (point<n && !set.contains(s.charAt(point))){
               set.add(s.charAt(point));
               point++;
           }
           max = Math.max(max,(point - i));
       }
       return max;
    }

    public static int lengthOfLongestSubstring2(String s){
        if(s.length()<=0 || s==null){
            return 0;
        }
        int[] array = new int[256];
        int window = 0;
        int max = 0;
        int n = s.length();
        for(int i=0;i<n;i++){
            int chr = s.charAt(i);
            window = Math.max(window,array[chr]);
            max = Math.max(max,i-window+1);
            array[chr] = i+1;
        }
        return max;
    }

    public static void main(String[] args) {
       String ss = "safwrwswercxs";
        System.out.println(lengthOfLongestSubstring2(ss));
    }
}
